#pragma once
#include <iostream>

using namespace std;
template<class T>
struct BSTNode
{

	T _val; 
	BSTNode<T>* _left;
	BSTNode<T>* _right;
	BSTNode(const T& x)
		:_val(x),
		_left(nullptr),
		_right(nullptr)
	{}
};
template<class T>
class BSTree
{
public:
	using Node = BSTNode<T>;
	bool find(const T& x)
	{
		
		Node* cur = _root;
		while (cur)
		{
			if (cur->_val < x)
			{
				cur = cur->_right;
			}
			else if (cur->_val > x)
			{
				cur = cur->_left;
			}
			else
			{
				return true;
			}
		}
		return false;
	}
	bool insert(const T& x)
	{
		if (_root == nullptr)
		{
			_root = new Node(x);
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_val < x)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_val > x)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		Node* newnode = new Node(x);
		if (parent->_val < x)
		{
			parent->_right = newnode;
		}
		else
		{
			parent->_left = newnode;
		}
		return true;
	}
	bool erase(const T& x)
	{
		Node* cur = _root;
		Node* parent = nullptr;

		while (cur)
		{
			if (cur->_val < x)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_val > x)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				if (cur->_left == nullptr)
				{
					if (parent == nullptr)
					{
						_root = cur->_right;
					}
					else if (parent->_left == cur)
					{
						parent->_left = cur->_right;
					}
					else
					{
						parent->_right = cur->_right;
					}
					delete cur;

				}
				else if (cur->_right == nullptr)
				{
					if (parent == nullptr)
					{
						_root = cur->_left;
					}
					if (parent->_left == cur)
					{
						parent->_left = cur->_left;
					}
					else
					{
						parent->_right = cur->_left;
					}
					delete cur;
				}
				else
				{
					Node* rightmin = cur->_right;
					Node* rightminp = cur;
					while (rightmin->_left)
					{
						rightminp = rightmin;
						rightmin = rightmin->_left;
					}
					cur->_val = rightmin->_val;
					if (rightminp->_left == rightmin)
					{
						rightminp->_left = rightmin->_right;
					}
					else
					{
						rightminp->_right = rightmin->_right;
					}
					delete rightmin;
				}
				return true;
			}
		}
		return false;
	}
	void Inorder()
	{
		Inorder(_root);
		cout << endl;
	}
	void Inorder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		Inorder(root->_left);
		cout << root->_val << ' ';
		Inorder(root->_right);

	}
private:
	Node* _root = nullptr;
};
//template<class K,class V>
//struct BSTNode
//{
//
//	K _key;
//	V _value;
//	BSTNode<K,V>* _left;
//	BSTNode<K,V>* _right;
//	BSTNode(const K& key = K(),const V& value = V())
//		:_key(key),
//		_value(value),
//		_left(nullptr),
//		_right(nullptr)
//	{}
//};
//template<class K,class V>
//class BSTree
//{
//public:
//	using Node = BSTNode<K,V>;
//	bool find(const K& key)
//	{
//
//		Node* cur = _root;
//		while (cur)
//		{
//			if (cur->_key < key)
//			{
//				cur = cur->_right;
//			}
//			else if (cur->_key > key)
//			{
//				cur = cur->_left;
//			}
//			else
//			{
//				return true;
//			}
//		}
//		return false;
//	}
//	bool insert(const K& key,const V& value)
//	{
//		if (_root == nullptr)
//		{
//			_root = new Node(key,value);
//			return true;
//		}
//		Node* cur = _root;
//		Node* parent = nullptr;
//		while (cur)
//		{
//			if (cur->_key < key)
//			{
//				parent = cur;
//				cur = cur->_right;
//			}
//			else if (cur->_key > key)
//			{
//				parent = cur;
//				cur = cur->_left;
//			}
//			else
//			{
//				return false;
//			}
//		}
//		Node* newnode = new Node(key,value);
//		if (parent->_key < key)
//		{
//			parent->_right = newnode;
//		}
//		else
//		{
//			parent->_left = newnode;
//		}
//		return true;
//	}
//	bool erase(const K& key)
//	{
//		Node* cur = _root;
//		Node* parent = nullptr;
//
//		while (cur)
//		{
//			if (cur->_key < key)
//			{
//				parent = cur;
//				cur = cur->_right;
//			}
//			else if (cur->_key > key)
//			{
//				parent = cur;
//				cur = cur->_left;
//			}
//			else
//			{
//				if (cur->_left == nullptr)
//				{
//					if (parent == nullptr)
//					{
//						_root = cur->_right;
//					}
//					else if (parent->_left == cur)
//					{
//						parent->_left = cur->_right;
//					}
//					else
//					{
//						parent->_right = cur->_right;
//					}
//					delete cur;
//
//				}
//				else if (cur->_right == nullptr)
//				{
//					if (parent == nullptr)
//					{
//						_root = cur->_left;
//					}
//					if (parent->_left == cur)
//					{
//						parent->_left = cur->_left;
//					}
//					else
//					{
//						parent->_right = cur->_left;
//					}
//					delete cur;
//				}
//				else
//				{
//					Node* rightmin = cur->_right;
//					Node* rightminp = cur;
//					while (rightmin->_left)
//					{
//						rightminp = rightmin;
//						rightmin = rightmin->_left;
//					}
//					cur->_key = rightmin->_key;
//					if (rightminp->_left == rightmin)
//					{
//						rightminp->_left = rightmin->_right;
//					}
//					else
//					{
//						rightminp->_right = rightmin->_right;
//					}
//					delete rightmin;
//				}
//				return true;
//			}
//		}
//		return false;
//	}
//	void Inorder()
//	{
//		Inorder(_root);
//		cout << endl;
//	}
//	void Inorder(Node* root)
//	{
//		if (root == nullptr)
//		{
//			return;
//		}
//		Inorder(root->_left);
//		cout << root->_key << ':' << root->_value << endl;
//		Inorder(root->_right);
//	}
//private:
//	Node* _root = nullptr;
//};